bzoj 2002 [Hnoi2010]Bounce 弹飞绵羊 题解

发表于 | 分类于 | | 热度: ℃

Description

有 $n$ 个排成一行的弹力装置。第 $i$ 个弹力装置的弹力系数是 $k_i$，它会把绵羊弹到第 $i+k_i$ 个装置上。如果不存在第 $i+k_i$ 个装置，绵羊被弹飞。

$m$ 次询问，有两种操作：$opt=1$: 输入一个数 $i$，查询绵羊从第 $i$ 个装置开始需要多少次被弹飞；$opt=2$: 输入两个数 $i$ 和 $j$，表示将装置 $i$ 的弹力系数改为 $j$。

数据范围：$n<=200000, m<=100000$

Solution

对 $n$ 个数进行分块。维护每个点 弹出所在块需要的次数 和 弹出后落在哪个节点上。从后往前扫描，方便每个节点继承后面节点的值。

预处理出所有点维护的信息，复杂度为 $O(n)$。修改 $i$ 节点的值时，不难发现与其有关的是当前块内编号比 $i$ 小的所有节点。修改这些节点维护的值。

最终复杂度为 $O(mlog_n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 200100;
int n, m, x, y, e = 0, f = 1, opt, unit, t[N], be[N];
struct node
{
    int num, id;
} cnt[N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return x * f;
}

void update(int l, int r)
{
    for(int i = r; i >= l; i--)
    {
        if(be[i + t[i]] == be[i]) cnt[i].num = cnt[i + t[i]].num + 1, cnt[i].id = cnt[i + t[i]].id;
        else cnt[i].num = 1, cnt[i].id = i + t[i];
    }
}

int main()
{
    n = read(), unit = sqrt(n);
    memset(be, 0, sizeof(be));
    for(int i = 1; i <= n; i++)
    {
        t[i] = read();
        e++;
        if(e == unit + 1) { f++; e = 1; }
        be[i] = f;
    }
    update(1, n);
    m = read();
    for(int i = 1; i <= m; i++)
    {
        opt = read(), x = read(); x++;
        if(opt == 1)
        {
            int now = x, tot = 0;
            while(now <= n)
            {
                tot += cnt[now].num;
                now = cnt[now].id;
            }
            printf("%d\n", tot);
        }
        else
        {
            y = read();
            t[x] = y;
            update(unit * (be[x] - 1) + 1, x);
        }
    }
    return 0;
}